In IP routing devices of an IP communications network, an IP packet is forwarded based on the destination IP address specified in the IP packet. In order to more efficiently manage routing of IP packets, classless inter-domain routing (CIDR) is performed based on a portion of the destination IP address which is typically a prefix having a bit length smaller than the total bit length of the destination IP address. Often, groups of IP packets with identical prefixes are forwarded together over the same destination port by using a routing table with summary IP addresses. A summary IP address specifies a prefix having a particular length which is used to route IP packets. For example a router may contain a table having a summary IP address determining the routing of IP packets having IP destination addresses which have identical 24-bit long prefixes of “138.120.52”. The summary IP address in the routing device table is denoted as 138.120.52.0/24, where the /24 indicates that this routing entry only applies to the first 24-bits of the destination IP address and the last “0” is merely a place-marker. If more than one summary IP address routing entry applies to an IP packet, for example 138.120.52.0/24 and 138.120.52.78/32, the IP packet is routed based on the summary IP address having the longest prefix of the matched IP packet. As such, an IP packet is said to be routed based on the longest prefix match (LPM) between the IP destination address of the IP packet and the summary IP addresses in the routing table. Due to the format of IP addresses, the longest prefix match corresponds to the most specific routing of the IP packets.
In hardware, a destination port lookup or routing lookup may be performed with use of a TCAM (ternary content addressable memory).
Content addressable memory (CAM) provides for an operation inverse to that of standard address access memory. Instead of returning data content from an address in the memory when passed the memory address, the CAM returns a particular memory address when passed the content data which matches content stored in the CAM at that memory address. If more than one address in the CAM contains the same data as that passed to it, that is if there is more than one entry in the CAM which matches the passed content data, the CAM will return a single address of a matching entry depending upon the algorithm performed by the CAM. The fastest CAMs either always return the lowest address of the entries which match the data or always return the highest address of the entries which match the data.
Ternary content addressable memory allows for the entry stored at each address in the TCAM to include data comprising 1s, 0s, and a third “don't care” value at each “bit” position. When data passed to the TCAM matches an entry at all bit positions of that entry having 1s and 0s, the TCAM will treat this as a complete match regardless of the bits of the data passed in the bit positions corresponding to the “don't care value” bit positions of the TCAM entry. In a TCAM, when there are multiple-matches, an arbiter of the TCAM returns a single TCAM address according to a fixed algorithm. For the purpose of IP forwarding, the TCAM is populated with summary IP address entries corresponding to destination IP addresses at TCAM addresses which are used to determine to which port a packet having that destination IP address is to be forwarded. TCAMs are ideal for use with summary IP addresses because of their ability to handle summary or partial data, which in this application are the prefixes of IP addresses used for routing. To be used effectively in routing IP packets, a summary IP address is stored in a TCAM in a manner such that the bits of an IP address not specified by the summary IP address are filled with “don't care” values in the TCAM entry. In order to ensure proper forwarding of IP packets which have different prefix lengths but identical specified bit values, the entries in the TCAM must be arranged so that depending upon the multiple matching algorithm of the arbiter of the TCAM, the TCAM address corresponding to the LPM is returned. This is achieved in fast TCAMs by having the summary IP address having the longest prefix either above or below the summary IP address having the smaller prefix so that the TCAM address of the summary IP address with the longest prefix is returned.
In general the particular application a TCAM is to be used for will dictate the type of sorting required. TCAM vendors often provide software sorters or table managers in a software support package bundled with their TCAMs. In the case of TCAMs used in IP routing, the TCAM sorting software provided typically sorts the TCAM so that the LPM is returned when the TCAM is passed a destination IP address. In general a sorter or table manager may be implemented in software or hardware to sort the TCAM according to the particular application for which it is used.
It should be understood that no matter what method is used to sort IP routing entries in a TCAM, it is always desirable to perform as few sorting operations or moves (such as add, delete, and shift) as possible. A few main reasons for this is that sorting operations in the TCAM can reduce the real time search bandwidth available for high data rate packet flow, and that the sorter or table manager performing the sorting operations on the TCAM require CPU resources.
FIG. 1 shows an example known TCAM 10 used for IP routing having M TCAM entries and which returns the lowest TCAM address in the case of a multiple match. The routing entries of the TCAM 10 are sorted according to a simple known method of sorting summary IP addresses in a TCAM for IP routing, namely, all routing entries are sorted in the TCAM 10 in order of prefix length. Starting at TCAM address 0, all summary IP addresses having 32-bit prefixes 2 are stored at the top of the table, next summary IP addresses having 31-bit prefixes 4, and so on down to summary IP addresses having 8-bit prefixes 6, ending at entry M−1. In FIG. 1, 7-bit prefixes and lower are not shown since prefixes of these lengths are not typically used in known routing tables with the exception of the default route or the 0.0.0.0/0 entry which is the route chosen when no other route matches. This entry is not shown in the table because this function is typically performed outside of the routing table, and in many applications when an IP packet has no match it is simply dropped. The TCAM 10 of FIG. 1 is shown as having a full routing table which cannot accept any more entries. Sorting in the order of the longest prefix length at the lowest TCAM address to the smallest prefix length at the highest TCAM address ensures that the LPM is always returned.
FIG. 2 depicts known sorting of a TCAM 10 similar to FIG. 1 with the addition of empty TCAM entries referred to as empty space 8, kept at the bottom of the TCAM 10. In this method, whenever a new summary IP address is added to the TCAM 10 at a particular TCAM address, all non-empty TCAM entries below that particular TCAM address are shifted in the TCAM downwards by 1, and whenever a summary IP address is removed from the TCAM 10 at a particular address, all non-empty TCAM entries below that particular address are shifted in the TCAM 10 upwards by 1. In the worst case, in the limit of the TCAM 10 becoming full, the number of moves required to properly sort entries in the TCAM 10 after an addition or deletion of a routing entry, is equal to the number of TCAM entries M of the TCAM 10.
FIG. 3 depicts known sorting of a TCAM 10 similar to that of FIG. 2 with the addition of empty space 8 between groups of non-empty TCAM entries having the same prefix length. As shown, there is empty space 8 between the 32-bit prefix entries 2 and the 31-bit prefix entries 4, between the 31-bit prefix entries 4 and the 30-bit prefix entries (not shown), and so on down to the empty space between the 9-bit prefix entries 7 and the 8-bit prefix entries 6. Whenever a new summary IP address is added to the TCAM 10, it is added to an empty entry adjacent to the group of routing entries having the same prefix bit length as the new summary IP address. If there are no spaces available, a non-empty entry of a neighboring group is shifted to an opposite side of the neighboring group to make an empty entry. At worst, 25 moves (32 minus 7) would have to be made to add a new summary IP address. Whenever a summary IP address is removed from the TCAM 10 from a particular group of routing entries, an entry on the edge of that particular group is moved to the empty space left by the removed summary IP address.
FIG. 4 depicts another known method of sorting a TCAM 10 similar to that of FIG. 1 with the addition of empty space 8 in the middle of the table, between the 21-bit prefix entries 3 and the 20-bit prefix entries 5. Although no spaces are shown between the groups of entries, the TCAM 10 of FIG. 4 having empty space midway in the table may have empty spaces between groups as well. Whether or not the TCAM 10 has spaces throughout, having a large empty space in the middle of the TCAM 10 halves the number of worst case moves required by dividing the problem in two. The sorting of entries above the space involves utilizing the space below it, while the sorting of entries below the space involves utilizing the space above it.
A more processing intensive variation of the method of sorting of FIG. 4 retains the empty space 8 in the middle of the TCAM 10 but dispenses with ordering groups of summary IP address entries by prefix length. Only summary IP addresses which are related to each other (i.e. have prefixes which are subsets or supersets of each other) need to be ordered in the TCAM 10, and moreover they need only be ordered with respect to each other. Unrelated summary IP addresses need not be ordered with respect to each other regardless of the length of their prefixes. Although this known method works in the sense that once the TCAM 10 is sorted it successfully returns the LPM, this known method involves a significant amount of overhead to keep track of how TCAM entries are related to each other and to ensure that the entries are sorted properly as the table of entries dynamically changes.
Currently, although known solutions succeed in sorting the TCAM entries so that IP packets are forwarded according to the LPM with use of the TCAM, they are deficient in a number of key ways. Many of the known solutions do not scale well to the wider IPv6 (Internet Protocol version 6) addresses which are 128 bits in length compared to IPv4 (Internet Protocol version 4) whose addresses are 32 bits long. Known solutions do not take into account real-world usage of IP networks and the statistical distribution of summary IP addresses normally found in routing devices. Some known solutions are overly complex and make inefficient use of resources and processing. Finally, none of the known solutions are specifically adaptive to the real-world networking and routing conditions that the TCAM is operating within.